//
// Created by shenbin on 2022/4/16.
// https://leetcode-cn.com/problems/merge-sorted-array/submissions/
//

#ifndef ALGORITHM_TRAINNING_C01_LC88_H
#define ALGORITHM_TRAINNING_C01_LC88_H

#include<vector>

using namespace std;

class LeetCode88 {
public:
    /**
     * 方法一，此方法为倒序方法；
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
        int i = m - 1, j = n - 1;
        //反着取
        for (int k = m + n - 1; k >= 0; k--) {
            //什么时候要nums1[i], j越界了或者i不越界，且nums1[i]大于nums2[j]
            if (j < 0 || (i >= 0 && nums1[i] > nums2[j])) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
        }
    }

    /**
     * 方法二：开辟一个新的数组来存放合并的数据，完成以后在将数组拷贝至原数组；
     * @param nums1
     * @param m
     * @param num2
     * @param n
     */
    void merge2(vector<int> &nums1, int m, vector<int> &num2, int n) {
        vector<int> result;
        int i = 0;
        int j = 0;
        while (i < m || j < n) {
            // 什么时候要nums1[i]？j 出界，或者i、j都没有出界 且 nums1[i] < nums2[j]
            // 第二个条件中完整的是：(i < m && j < n && nums1[i] < nums2[j]，但，当第一个条件成立时就过滤了j<n的情况；
            if (j >= n || (i < m && nums1[i] < nums2[j])) {
                result.push_back(nums1[i]);
                i++;
            } else {
                result.push_back(nums2[j]);
                j++;
            }
        }
        for (int i = 0; i < m + n; i++) {
            nums1[i] = result[i];
        }
    }

    /**
     * 方法三：将nums2的元素拷贝至nums1，然后使用sort方法排序；
     * @param nums1 数组1，尾部有足够的空间容纳数组2
     * @param m
     * @param nums2
     * @param n
     */
    void merge3(vector<int>& nums1, int m, vector<int>& nums2 , int n)
    {
        int i = n-1;
        while(i >=0)
        {
            nums1[m+i] = nums2[i];
            i--;
        }
        sort(nums1.begin(), nums1.end());
    }

};

#endif //ALGORITHM_TRAINNING_C01_LC88_H
